We derive tight bounds on the expected weights of several combinatorialoptimization problems for random point sets of size $n$ distributed among theleaves of a balanced hierarchically separated tree. We consider {\itmonochromatic} and {\it bichromatic} versions of the minimum matching, minimumspanning tree, and traveling salesman problems. We also present tightconcentration results for the monochromatic problems.
展开▼
机译：对于分布在平衡的分层分离树的叶子之间的大小为$ n $的随机点集，我们得出了几个组合优化问题的预期权重的严格边界。我们考虑最小匹配，最小生成树和旅行商问题的{\ itmonochrome}和{\ it双色}版本。我们还给出了单色问题的紧密浓度结果。
展开▼
